/*
 * @lc app=leetcode.cn id=46 lang=cpp
 *
 * [46] 全排列
 */

// @lc code=start
// class Solution {
// public:
//     void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len) {
//         if (first == len) {
//             res.emplace_back(output);
//             return;
//         }
//         for (int i = first; i < len; ++i) {
//             swap(output[first], output[i]);
//             backtrack(res, output, first + 1, len);
//             swap(output[first], output[i]);
//         }
//     }
//     vector<vector<int>> permute(vector<int>& nums) {
//         vector<vector<int>> res;
//         backtrack(res, nums, 0, (int)nums.size());
//         return res;
//     }
// };


class Solution {
    vector<bool> used;
    vector<int> track;
    vector<vector<int>> res;

    void backtrack(vector<int>nums) {
        if (track.size() == nums.size()) {
            res.emplace_back(track);
            return;
        }

        for (int i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;

            used[i] = true;
            track.emplace_back(nums[i]);
            backtrack(nums);
            track.pop_back();
            used[i] = false;
        }
    }


public:
    vector<vector<int>> permute(vector<int>& nums) {
        used.resize(nums.size());
        backtrack(nums);
        return res;     
    }
};
// @lc code=end

